FPS24 D - 数列 2
数列の要素は相異なるので、単調増加なものを数えて後で$ N!倍すればよい。
条件は「階差が奇数となる」と言い換えられる。(最初の要素, 階差...) の母関数を書き下すと、$ (1+x+x^2+\cdots)(x+x^3+x^5+\cdots)^{N-1} となり、$ x^0,x^1,\cdots,x^Mの係数の総和が求める答えである。
上式を整理して、$ \frac{x^{N-1}}{(1-x)(1-x^2)^{N-1}}つまり $ \frac{1}{(1-x)(1-x^2)^{N-1}}の $ x^0, \cdots, x^{M-N+1} の係数の総和を求めればよい。 $ \frac{1}{(1-x^2)^{N-1}}を負の二項定理で必要な分展開し、累積和を取ることで係数がそれぞれ求まる。